package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2021/3/30
 * @description: 687. 最长同值路径
 * https://leetcode-cn.com/problems/longest-univalue-path/
 * 记忆化搜索，这道题简直是二叉树的DP
 */
public class B_687_最长同值路径 {

	static B_687_最长同值路径 action = new B_687_最长同值路径();

	public static void main(String[] args) {
//		test1();
		test3();
	}

	static void test1() {
		TreeNode node = TreeNode.stringToTreeNode("[5,4,5,1,1,5]");
		int res = action.longestUnivaluePath(node);
		System.out.println("res = " + res);
	}

	static void test2() {
		TreeNode node = TreeNode.stringToTreeNode("[1,2,3,4,2]");
		int res = action.longestUnivaluePath(node);
		System.out.println("res = " + res);
	}

	static void test3() {
		TreeNode node = TreeNode.stringToTreeNode("[1,null,1,1,1,1,1,1]");
		int res = action.longestUnivaluePath(node);
		System.out.println("res = " + res);
	}

	/**
	 * 最后的结果
	 */
	int res = 0;

	/**
	 * 其实这种递归的思路很像DP
	 *
	 * @param root
	 * @return
	 */
	public int longestUnivaluePath(TreeNode root) {
		int rootPath = getMaxLen(root);
		return Math.max(rootPath, res);
	}


	private int getMaxLen(TreeNode node) {
		if (node == null) {
			return 0;
		}
		int leftPath = node.left == null ? 0 : getMaxLen(node.left);
		int rightPath = node.right == null ? 0 : getMaxLen(node.right);

		int ans = 0;
		if (node.left != null && node.right != null) {
			//如果左右节点都在
			if (node.left.val == node.val && node.right.val == node.val) {
				//并且跟左右节点都相等
				res = Math.max(res, leftPath + rightPath + 2);
				ans = Math.max(leftPath,rightPath)+1;
			} else if (node.left.val == node.val) {
				//只有 left 相等
				//ans =Math.max(ans, leftPath+1);
				ans = leftPath + 1;
			} else if (node.right.val == node.val) {
				ans = rightPath + 1;
			} else {
				//都不相等
				res = Math.max(rightPath, res);
				res = Math.max(leftPath, res);
				ans = 0;
			}
		} else if (node.left != null) {
			//只有 left
			if (node.left.val == node.val) {
				ans = leftPath + 1;
			} else {
				res = Math.max(leftPath, res);
			}
			//ans = node.left.val == node.val ? leftPath + 1 : 0;
		} else if (node.right != null) {
			//只有 right
			if (node.right.val == node.val) {
				ans = rightPath + 1;
			} else {
				res = Math.max(rightPath, res);
			}
			//ans = node.right.val == node.val ? rightPath + 1 : 0;
		}
		return ans;

	}
}
